/*
 * Créé le 21 mars 06
 */
package fr.cdesire.sudoku.elements;

import fr.cdesire.sudoku.elements.exceptions.NotSudokuSolutionException;
import fr.cdesire.sudoku.elements.exceptions.NotValidSudokuGridException;
import fr.cdesire.sudoku.utils.ArbreEtats;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.Stack;
import java.util.TreeSet;

/**
 * @author Cedric
 */
public class Sudoku {

    /**
     * Nombre de cases pour un côté d'une région de Sudoku.
     */
    public static final int NB_CASES_LIGNE_REGION = 3;
    /**
     * Nombre de cases pour un côté d'une grille de Sudoku.
     */
    public static final int NB_CASES_LIGNE_GRILLE = 9;
    private static ArbreEtats arbre = new ArbreEtats();
    private SortedSet casesVides;
    private List casesPleines;
    private int[][] grille;

    // Recherche l'index de la région correspondante aux coordonn�es
    // passées en paramètres.
    private static int posRegion(int posLigne, int posCol) {
        return (posLigne / NB_CASES_LIGNE_REGION) * NB_CASES_LIGNE_REGION + posCol / NB_CASES_LIGNE_REGION;
    }

    // Recherche l'index d'une valeur dans une région correspondante
    // aux coordonnées passées en paramètres.
    private static int posValDansRegion(int posLigne, int posCol) {
        return (posLigne % NB_CASES_LIGNE_REGION) * NB_CASES_LIGNE_REGION + posCol % NB_CASES_LIGNE_REGION;
    }

    /**
     * Méthode statique récursive de recherche d'une solution de
     * Sudoku.
     * @param sudoku Sudoku source.
     * @return Solution de Sudoku.
     * @throws NotSudokuSolutionException Solution inexistante.
     */
    public static Sudoku rechercheSolution(Sudoku sudoku)
            throws NotSudokuSolutionException {

        if (sudoku.casesVides.isEmpty()) {
            return sudoku;
        }

        Stack sudokusPossibles = new Stack();
        Case caseVide = (Case) sudoku.getCasesVides().first();
        Iterator iter = caseVide.getPossibilites().iterator();

        while (iter.hasNext()) {

            int[][] grille = new int[NB_CASES_LIGNE_GRILLE][NB_CASES_LIGNE_GRILLE];

            for (int i = 0; i < NB_CASES_LIGNE_GRILLE; i++) {
                for (int j = 0; j < NB_CASES_LIGNE_GRILLE; j++) {
                    grille[i][j] = sudoku.getGrille()[i][j];
                }
            }
            grille[caseVide.getPosLigne()][caseVide.getPosColonne()] = ((Integer) iter.next()).intValue();
            sudokusPossibles.push(new Sudoku(grille));
        }

        try {
            return rechercheSolution((Sudoku) arbre.getEtat(sudokusPossibles));
        } catch (EmptyStackException e) {
            throw new NotSudokuSolutionException("Il n'existe pas de solutions possibles");
        }
    }

    /**
     * Appel du constructeur de Sudoku.
     * @param grille Grille des valeurs du Sudoku (par ligne, puis
     * par colonne).
     */
    public Sudoku(int[][] grille) {

        this.grille = grille;

        casesVides = new TreeSet();
        casesPleines = new ArrayList();

        // Réorganisation de la grille sous forme de tableau de
        // lignes, tableau de colonnes, tableau de régions.
        ArrayList lignes = new ArrayList();
        ArrayList colonnes = new ArrayList();
        ArrayList regions = new ArrayList();

        for (int i = 0; i < NB_CASES_LIGNE_GRILLE; i++) {

            ArrayList ligne = new ArrayList();
            ArrayList colonne = new ArrayList();
            ArrayList region = new ArrayList();

            for (int j = 0; j < NB_CASES_LIGNE_GRILLE; j++) {

                ligne.add(new Integer(this.grille[i][j]));
                colonne.add(new Integer(this.grille[j][i]));
                region.add(new Integer(this.grille[posRegion(i, j)][posValDansRegion(i, j)]));
            }

            lignes.add(ligne);
            colonnes.add(colonne);
            regions.add(region);
        }

        // Création des cases et alimentation des tableaux
        // casesPleines et casesVides.
        for (int i = 0; i < NB_CASES_LIGNE_GRILLE; i++) {
            for (int j = 0; j < NB_CASES_LIGNE_GRILLE; j++) {
                Case caseSudoku = new Case(i, j, grille[i][j], (ArrayList) lignes.get(i), (ArrayList) colonnes.get(j), (ArrayList) regions.get(posRegion(i, j)));
                if (caseSudoku.isVide()) {
                    casesVides.add(caseSudoku);
                } else {
                    casesPleines.add(caseSudoku);
                }
            }
        }
    }

    /**
     * Valide la grille de Sudoku sinon lève une exception en
     * indiquant les cases non valides.
     * @throws NotValidSudokuGridException Grille non valide.
     */
    public void validation() throws NotValidSudokuGridException {

        for (int i = 0; i < casesPleines.size() - 1; i++) {

            Case case1 = (Case) casesPleines.get(i);

            for (int j = i + 1; j < casesPleines.size(); j++) {

                Case case2 = (Case) casesPleines.get(j);

                if (case1.getValeur() == case2.getValeur()) {

                    if (case1.getPosLigne() == case2.getPosLigne()) {
                        throw new NotValidSudokuGridException(
                                "Ligne " + (case1.getPosLigne() + 1) + " invalide aux colonnes "
                                + (case1.getPosColonne() + 1) + " et " + (case2.getPosColonne() + 1));
                    }

                    if (case1.getPosColonne() == case2.getPosColonne()) {
                        throw new NotValidSudokuGridException(
                                "Colonne " + (case1.getPosColonne() + 1) + " invalide aux lignes "
                                + (case1.getPosLigne() + 1) + " et " + (case2.getPosLigne() + 1));
                    }

                    if (posRegion(case1.getPosLigne(), case1.getPosColonne()) == posRegion(case2.getPosLigne(), case2.getPosColonne())) {
                        throw new NotValidSudokuGridException(
                                "Region invalide en (" + (case1.getPosLigne() + 1) + ", "
                                + (case1.getPosColonne() + 1) + ") et (" + (case2.getPosLigne() + 1) + ", "
                                + (case2.getPosColonne() + 1) + ")");
                    }
                }
            }
        }
    }

    /**
     * Grille du Sudoku.
     * @return Grille du Sudoku.
     */
    public int[][] getGrille() {
        return this.grille;
    }

    /**
     * Cases vides du Sudoku.
     * @return Cases vides du Sudoku.
     */
    public SortedSet getCasesVides() {
        return this.casesVides;
    }
}
